// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-25 14:31
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.ArraysTrain.preFixTrain;

import org.junit.jupiter.api.Test;

import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;

public class KthLargestValue {
    /**
     * 找出二维矩阵中异或操作之后的第K大数字
     * 二维前缀和 + 优先队列
     */
    public int kthLargestValue(int[][] matrix, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(k, (a, b) -> a - b);
        /*-----前缀和二维数组构建-----*/
        int n = matrix.length, m = matrix[0].length;
        int[][] preFix = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                preFix[i][j] = preFix[i - 1][j] ^ preFix[i][j - 1] ^ preFix[i - 1][j - 1] ^ matrix[i - 1][j - 1];
                if (queue.size() < k) {
                    queue.add(preFix[i][j]);
                } else {
                    if (preFix[i][j] > queue.peek()) {
                        queue.poll();
                        queue.add(preFix[i][j]);
                    }
                }
            }
        }
        return queue.peek();
    }


    @Test
    public void shout() {
        //int[][] test = {{5, 2}, {1, 6}};
        int[][] test = {{3, 10, 9, 5, 5, 7}, {0, 1, 7, 3, 8, 1}, {9, 3, 0, 6, 1, 6}, {10, 2, 9, 10, 10, 7}};
        System.out.println(kthLargestValue(test, 18));
    }
}
